//
// Created by xili on 2024/8/30 21:07.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution1 {
public:
    int maxIceCream(vector<int> &costs, int coins) {
        sort(costs.begin(), costs.end());
        int n = costs.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (coins - costs[i] >= 0) {
                coins -= costs[i];
                ans++;
            } else {
                break;
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    int maxIceCream(vector<int> &costs, int coins) {
        int cnt[100001] = {0};
        int n = costs.size();
        for (int i = 0; i < n; i++) {
            cnt[costs[i]]++;
        }
        int ans = 0;
        for (int i = 1; i < 100001; i++) {
            if (coins >= i && cnt[i]) {
                int cur = min(cnt[i], coins / i);
                ans += cur;
                coins -= i * cur;
            } else if (coins < i) {
                break;
            }
        }
        return ans;
    }
};